package com.interview03;

/**
 * Copyright (C), 2018-2020
 * FileName: Demo5
 * Author:   kongfanyu
 * Date:     2020/12/21 09:10
 */
public class Demo5 {
    public static void main(String[] args) {
        Demo5 demo5 = new Demo5();
        ListNode listNode = demo5.createListNode(10);
        ListNode listNode1 = demo5.FindKthToTail(listNode, 4);
        System.out.println(listNode1.val);
    }
    //创建链表
    public ListNode createListNode(int size){
        ListNode head = new ListNode(1);//头节点是1 ； 1->2->3->4->5->6->7->8->9->10
        ListNode curr = head;//声明一个current节点
        for (int i = 2;i <= size; i++){
            ListNode node = new ListNode(i);//3
            curr.next = node;
            curr = node;//curr指向的是2
        }
        return head;
    }

    public int size(ListNode head) {  //求出链表的长度
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            size++;
            cur = cur.next;
        }
        return size;
    }

    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null) {   //如果是空链表直接返回null
            return null;
        }
        int size = size(head);  //用size方法求出该链表的长度
        if (k <= 0 || k > size) {
            // k 是非法值
            return null;
        }
        int steps = size - k;  //从头开始走steps步数后的节点即为要求节点
        ListNode cur = head;
        for (int i = 0; i < steps; i++) {
            cur = cur.next;
        }
        return cur;
    }
}
